package leetcode; /**
 * description:
 * author:张腾
 * date:2021-07-02
 */

import java.util.Arrays;

/**
 * 给你一个整数数组 nums，请你将该数组升序排列。
 */
//快排
public class leetcode912 {
    public int[] sortArray(int[] nums) {
        int[] ans = quickSort(nums, 0, nums.length - 1);
        return ans;
    }

    private int[] quickSort(int[] nums, int left, int right) {
        if(left<right){
            int partition = partition(nums,left,right);
            quickSort(nums,left,partition-1);
            quickSort(nums,partition+1,right);
        }
        return nums;
    }

    public int partition(int[] nums,int left,int right){
        int l = left, r = right;
        int p = nums[left];
        while (l<r){
            while (nums[r]>p && l<r) r--;
            while (nums[l]<=p && l<r) l++;

            if (l<r){
                int tmp = nums[l];
                nums[l] = nums[r];
                nums[r] = tmp;
            }
        }
        nums[left] = nums[r];
        nums[r] = p;
        return r;
    }
}
